/**
 * 优先算法：2 - 4题
 */
public class Main{
    /**
     * 复写0
     *https://leetcode.cn/problems/duplicate-zeros/
     */
    public static void duplicateZeros(int[] arr) {

        //1.定义变量
        int dest = -1,cur = 0,len = arr.length;

        //2.找到最后一个复写的位置
        while(cur < len){
            if(arr[cur] != 0){
                dest++;
            }else{
                dest += 2;
            }
            //如果dest已经到达末尾，cur就是最后一个复写位置
            if(dest >= len) break;
            cur++;
        }
        //3.处理边界情况
        if(dest == len){
            cur -= 1;
            arr[dest - 1] = 0;
            dest -= 2;
        }

        //4.从后往前复写
        for(;cur >= 0;cur--){
            if(arr[cur] != 0){
                arr[dest--] = arr[cur];
            }else{
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
        }
    }

    public static void main(String[] args) {
        Main.duplicateZeros(new int[]{1,2,0,3,0,4});
    }
}

class Solution {
    public void duplicateZeros(int[] arr) {

        //1.定义变量
        int dest = -1,cur = 0,len = arr.length;

        //2.找到最后一个复写的位置
        while(cur < len){
            if(arr[cur] != 0){
                dest++;
            }else{
                dest += 2;
            }
            if(dest >= len -1) break;
            cur++;
        }
        //3.处理边界情况
        if(dest == len){
            cur -= 1;
            arr[dest - 1] = 0;
            dest -= 2;
        }

        //3.从后往前复写
        for(;cur >= 0;cur--){
            if(arr[cur] != 0){
                arr[dest--] = arr[cur];
            }else{
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
        }
    }
}

/**
 * 快乐数
 * https://leetcode.cn/problems/happy-number/
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
class Solution2 {

    //获得每位平方和
    public int bigSum(int n){
        int sum = 0;
        while(n != 0){
            sum +=(n % 10) * (n % 10);
            n /=10;
        }
        return sum;
    }
   //快慢双指针：存在环必定相遇，判断相遇值是否为1
    public boolean isHappy(int n){

        int fast = bigSum(n),slow = n;
        while(fast != slow){
            fast = bigSum(bigSum(fast));
            slow = bigSum(slow);
        }
        return fast == 1;
    }
}

/**
 * 容量最多的水桶
 * https://leetcode.cn/problems/container-with-most-water/
 * 时间复杂度：O（n）
 * 空间复杂度：O（1）
 */
class Solution3 {

    public int maxArea(int[] height) {
        int left = 0,right = height.length -1,max = 0;
        while(left < right){
            max = Math.max(max,Math.min(height[left],height[right]) * (right - left));
            if(height[right] > height[left]) left++;
            else right--;
        }
        return max;
    }
}